package Kernel;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.GregorianCalendar;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * Cette classe a pour objectif de représenter un réseau de trajets ainsi que
 * les transports associés. Plusieurs opérations seront possibles telles que la
 * recherche d'itinéraires, avec ou sans correspondance.
 * 
 * @author Romain Roufast
 * 
 */
public class Reseau implements Serializable{

	/**
	 * Matrice des trajets
	 */
	private List<Trajet>[][] t;
	/**
	 * Villes appartenant au réseau
	 */
	private List<Ville> v;

	/**
	 * Construire le réseau de transport, càd les villes desservies et les
	 * trajets possibles. Sous forme d'une matrice[n][n], où "n" est le nombre
	 * de villes.
	 * 
	 */
	public Reseau(List<Ville> villes, List<Trajet> trajets) {
		t = (List<Trajet>[][]) new ArrayList[villes.size()][villes.size()];
		v = new ArrayList<Ville>();
		v = villes;
		construireMatrice(trajets);
	}

	/**
	 * Construire la matrice qui contient des listes de trajets ex :
	 * m[Nice][Paris] = List<Trajet>
	 */
	private void construireMatrice(List<Trajet> trajets) {
		// On parcourt les villes
		for (int i = 0; i < trajets.size(); i++) {
			Trajet tmp = trajets.get(i);
			int x = indiceVille(tmp.getVilleDepart());
			int y = indiceVille(tmp.getVilleArrivee());

			// On ajoute le trajet à la liste
			if (t[x][y] == null) {
				t[x][y] = new ArrayList<Trajet>();
			}
			t[x][y].add(trajets.get(i));
		}
	}

	/**
	 * 
	 * @param ville
	 *            la ville dont nous cherchons l'indice dans la matrice.
	 * 
	 * @return l'indice de la ville dans la matrice (car nous avons une matrice
	 *         carrée).
	 */
	private int indiceVille(Ville ville) {
		int indice = -1;
		for (int i = 0; i < v.size(); i++) {
			if (ville.getNom().equals(v.get(i).getNom())) {
				indice = i;
				break;
			}
		}
		return indice;
	}

	/**
	 * Savoir si deux villes sont en relation (directe ou indirecte), et
	 * connaître les itinéraires possibles.
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @return les différents itinéraires possibles
	 */
	private List<List<List<Trajet>>> connecte(Ville depart, Ville arrivee,
			boolean correspondance) {
		return connecte(t.length, depart, arrivee, correspondance);
	}

	/**
	 * Savoir si deux villes sont en relation (directe ou indirecte), et
	 * connaître les itinéraires possibles.
	 * 
	 * @param k
	 *            le nombre d'appels récursifs maximum (correspond à la hauteur
	 *            de la matrice)
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @return les différents itinéraires possibles
	 */
	private List<List<List<Trajet>>> connecte(int k, Ville depart,
			Ville arrivee, boolean correspondance) {
		int i = indiceVille(depart), j = indiceVille(arrivee);
		// Si le client veut un trajet direct
		List<List<Trajet>> l = new ArrayList<List<Trajet>>();
		List<List<List<Trajet>>> h = new ArrayList<List<List<Trajet>>>();
		if (correspondance == false) {
			if (t[i][j] != null) {
				l.add(t[i][j]);
				h.add(l);
				return h;
			} else
				return null;
		}

		// Recursivité, si le nombre de correspondances est supérieur à 4 on ne
		// prend pas en compte l'itinéraire
		if (k > 5)
			k = 5;
		rec(k, l, h, depart, arrivee, depart);

		return h;

	}

	/**
	 * Fonction recursive, trouve tous les trajets possibles (avec
	 * correspondance) à partir de deux villes
	 * 
	 * @param k
	 * @param l
	 * @param depart
	 * @param arrivee
	 * @param prec
	 * @return
	 */
	private boolean rec(int k, List<List<Trajet>> l,
			List<List<List<Trajet>>> h, Ville depart, Ville arrivee, Ville prec) {
		boolean b = false;
		if (k == 0)
			return b;
		int ind = indiceVille(depart);
		for (int i = 0; i < v.size(); i++) {
			if (t[ind][i] != null) {
				if ((v.get(i)).getNom().equals(arrivee.getNom())) {
					l.add(t[ind][i]);
					return true;
				}

				if (!(v.get(i).getNom().equals(prec.getNom()))) {
					b = rec(k - 1, l, h, v.get(i), arrivee, depart);
					if (b == true) {
						l.add(t[ind][i]);
						if (k == t.length) {
							List<List<Trajet>> tmp = new ArrayList<List<Trajet>>();
							for (List<Trajet> list : l) {
								tmp.add(list);
							}
							h.add(tmp);
							l.clear();
						}
					}
				}
			}
		}
		return b;
	}

	/**
	 * Afficher les itinéraires possibles en fonction de : - la ville de départ
	 * - la ville d'arrivée - si le voyageur souhaite une correspondance ou pas
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 */
	public void afficherItineraires(Ville depart, Ville arrivee,
			boolean correspondance) {

		// Liste des itinéraires possibles
		List<List<List<Trajet>>> h = obtenirItineraires(depart, arrivee,
				correspondance);
		afficher(h);
	}

	/**
	 * Afficher les itinéraires possibles en fonction de : - la ville de départ
	 * - la ville d'arrivée - si le voyageur souhaite une correspondance ou pas
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 */
	public void afficherItineraires(Ville depart, Ville arrivee) {

		// Liste des itinéraires possibles
		List<List<List<Trajet>>> h = obtenirItineraires(depart, arrivee);
		afficher(h);

	}

	/**
	 * Récupérer les itinéraires possibles suivant les villes de départ,
	 * d'arrivée et la correspondance.
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @return
	 */
	public List<List<List<Trajet>>> obtenirItineraires(Ville depart,
			Ville arrivee, boolean correspondance) {

		List<List<List<Trajet>>> l = new ArrayList<List<List<Trajet>>>();
		List<List<List<Trajet>>> tmp = connecte(depart, arrivee, correspondance);
		if (tmp != null)
			l.addAll(tmp);
		if (l != null)
			verifierItineraires(l);

		return l;
	}

	/**
	 * Récupérer les itinéraires possibles suivant les villes de départ,
	 * d'arrivée. (avec ou sans correspondance)
	 * 
	 * @param depart
	 * @param arrivee
	 * @return
	 */
	public List<List<List<Trajet>>> obtenirItineraires(Ville depart,
			Ville arrivee) {

		List<List<List<Trajet>>> l = new ArrayList<List<List<Trajet>>>();
		List<List<List<Trajet>>> tmp = obtenirItineraires(depart, arrivee,
				false);
		if ((tmp != null) && (tmp.size() > 0))
			l.add(tmp.get(0)); // indice 0 car itinéraire à un seul noeud fils
		// (ex : vol direct Paris->NY)
		tmp = obtenirItineraires(depart, arrivee, true);
		if (tmp != null)
			l.addAll(tmp);

		return l;
	}

	/**
	 * Vérifie/Corrige les itinéraires en fonction des dates
	 * 
	 * @param l
	 */
	private void verifierItineraires(List<List<List<Trajet>>> l) {

		GregorianCalendar dateAuPlusTot = null;
		Iterator it = l.iterator();
		while (it.hasNext()) {
			dateAuPlusTot = new GregorianCalendar(2012, 3, 26);
			List<List<Trajet>> list = (List<List<Trajet>>) it.next();
			for (int i = list.size() - 1; i >= 0; i--) {
				dateAuPlusTot = verifierDatesTrajets(dateAuPlusTot, list.get(i));
				if (dateAuPlusTot == null) { // <=> trajets.size() == 0
					it.remove();
					break;
				}
			}
			itinerairesPossibles(list);
		}
	}

	/**
	 * Si la date du trajet est inférieure à la date passée en paramètre, le
	 * trajet est supprimé de l'étape
	 * 
	 * @param date
	 * @param l
	 * @return la date minimum à partir de laquelle le prochain trajet peut-être
	 *         lancé
	 */
	private GregorianCalendar verifierDatesTrajets(GregorianCalendar date,
			List<Trajet> l) {

		GregorianCalendar dateRetour = null;
		Iterator it = l.iterator();
		while (it.hasNext()) {
			Trajet t = (Trajet) it.next();
			if (t.getDateDepart().before(date))
				it.remove();
			else {
				if (dateRetour == null) {
					dateRetour = new GregorianCalendar();
					dateRetour = t.getDateArrivee();
				} else if (t.getDateArrivee().before(dateRetour))
					dateRetour = t.getDateArrivee();
			}
		}

		return dateRetour;
	}

	/**
	 * Supprime les trajets pour lesquels la date d'arrivée est supérieure à la
	 * plus grande des dates de départ de l'étape suivante.
	 * 
	 * @param l
	 */
	private void itinerairesPossibles(List<List<Trajet>> l) {

		GregorianCalendar dateMax = null, tmpDate = null;
		int cmp = 0;
		boolean dateMiseAJour = false;
		for (int i = 0; i < l.size(); i++) {
			List<Trajet> list = l.get(i);
			Iterator<Trajet> it = list.iterator();
			while (it.hasNext()) {
				Trajet t = it.next();
				if (i == 0) {
					if (dateMax == null) {
						tmpDate = t.getDateDepart();
					} else {
						if (t.getDateDepart().after(dateMax))
							tmpDate = t.getDateDepart();
					}
				} else {
					if (t.getDateArrivee().after(dateMax))
						it.remove();
					else {
						if ((dateMiseAJour == false)
								|| t.getDateDepart().after(tmpDate)) {
							tmpDate = t.getDateDepart();
							dateMiseAJour = true;
						}
					}
				}
			}
			dateMax = tmpDate;
			dateMiseAJour = false;
		}
	}

	/**
	 * 
	 * @param l
	 * @param k
	 *            la profondeur voulue
	 * @return
	 */
	// essayer avec le constructeur de copie
	private List<List<Trajet>> extraireSousItineraire(List<List<Trajet>> l,
			int k) {

		List<List<Trajet>> sousItineraire = new ArrayList<List<Trajet>>();
		for (int i = 0; i < l.size() - k; i++) {
			List<Trajet> tmp = new ArrayList<Trajet>();
			for (int j = 0; j < l.get(i).size(); j++)
				tmp.add(l.get(i).get(j));
			sousItineraire.add(tmp);
		}
		return sousItineraire;
	}

	/**
	 * Parcourt l'ensemble des itinéraires et trouve le moins cher.
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @param reduction
	 *            , si le voyageur bénéficie d'une réduction
	 * @return un objet pour lequel o[0] = itinéraire au plus bas prix, et o[1]
	 *         le prix.
	 */
	public Object[] itineraireMoinsCher(Ville depart, Ville arrivee,
			double reduction) {

		List<List<List<Trajet>>> l = obtenirItineraires(depart, arrivee);
		if (l == null)
			return null;

		return parcourirItineraires(l, reduction);
	}

	/**
	 * Parcourt l'ensemble des itinéraires et trouve le moins cher.
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @param reduction
	 *            , si le voyageur bénéficie d'une réduction
	 * @return un objet pour lequel o[0] = itinéraire au plus bas prix, et o[1]
	 *         le prix.
	 */
	public Object[] itineraireMoinsCher(Ville depart, Ville arrivee,
			boolean correspondance, double reduction) {

		List<List<List<Trajet>>> l = obtenirItineraires(depart, arrivee,
				correspondance);
		if (l == null)
			return null;

		return parcourirItineraires(l, reduction);
	}

	/**
	 * 
	 * @param l
	 * @param reduction
	 *            , si le voyageur bénéficie d'une réduction
	 * @return
	 */
	private Object[] parcourirItineraires(List<List<List<Trajet>>> l,
			double reduction) {
		Object[] o = new Object[2];
		o[0] = null;
		for (List<List<Trajet>> list : l) {
			Object[] tmp = itineraireMoinsCher(list, reduction);
			List<List<Trajet>> itineraireMoinsCher = (List<List<Trajet>>) tmp[0];
			Double prixTotal = (Double) tmp[1];
			if ((o[0] == null) || (prixTotal < (Double) o[1]))
				o = tmp;
		}

		return o;
	}

	/**
	 * Trouver l'itinéraire le plus court
	 * 
	 * @param depart
	 * @param arrivee
	 * @return l'itinéraire le plus court
	 */
	public List<List<Trajet>> itinerairePlusCourt(Ville depart, Ville arrivee) {
		List<List<List<Trajet>>> l = obtenirItineraires(depart, arrivee);
		if (l == null || l.size() == 0)
			return null;

		return itinerairePlusCourt(l);
	}

	/**
	 * Trouver l'itinéraire le plus court
	 * 
	 * @param depart
	 * @param arrivee
	 * @param correspondance
	 * @return l'itinéraire le plus court
	 */
	public List<List<Trajet>> itinerairePlusCourt(Ville depart, Ville arrivee,
			boolean correspondance) {
		List<List<List<Trajet>>> l = obtenirItineraires(depart, arrivee,
				correspondance);
		if (l == null || l.size()==0)
			return null;

		return itinerairePlusCourt(l);
	}

	/**
	 * Trouver l'itinéraire le plus court
	 * 
	 * @param l
	 *            la liste des itinéraires
	 * @return l'itinéraire le plus court
	 */
	private List<List<Trajet>> itinerairePlusCourt(List<List<List<Trajet>>> l) {
		int indiceItinerairePlusCourt = 0, longueurTrajetPlusCourt = 0;
		for (int i = 0; i < l.size(); i++) {
			if ((i == 0) || (((l.get(i)).size()) < longueurTrajetPlusCourt)) {
				indiceItinerairePlusCourt = i;
				longueurTrajetPlusCourt = ((l.get(i)).size());
			}
		}

		return l.get(indiceItinerairePlusCourt);
	}

	/**
	 * Calcule le prix d'un itinéraire et renvoie celui qui est le moins cher
	 * 
	 * @param it
	 * @param reduction
	 *            , si le voyageur bénéficie d'une réduction
	 * @return un objet pour lequel o[0] = itinéraire au plus bas prix, et o[1]
	 *         le prix.
	 */
	private Object[] itineraireMoinsCher(List<List<Trajet>> it, double reduction) {
		Object[] o = new Object[2];
		List<List<Trajet>> l = it;
		Double prixTrajet = 0.0;
		Double prixTotal = 0.0;

		for (int i = 0; i < it.size(); i++) {
			List<Trajet> list = it.get(i);
			for (Trajet trajet : list) {
				if (((trajet.getTarif() * reduction) < prixTrajet)
						|| prixTrajet == 0) {
					prixTrajet = trajet.getTarif()
							- (trajet.getTarif() * reduction);
					l.set(i, new ArrayList<Trajet>());
					l.get(i).add(trajet);
				}
			}
			prixTotal += prixTrajet;
		}

		o[0] = l;
		o[1] = prixTotal;
		return o;
	}

	/**
	 * Affiche les itinéraires à partir d'une liste
	 * 
	 * @param h
	 *            la liste d'itinéraires
	 */
	private void afficher(List<List<List<Trajet>>> h) {
		System.out.println(getTrajetsAsString(h));
	}

	/**
	 * Récupérer les itinéraires sous forme de chaines de caractères
	 * 
	 * @param h
	 * @return la chaine de caractère représentant les différents itinéraires
	 */
	public String getTrajetsAsString(List<List<List<Trajet>>> h) {
		// Chaine resultat
		String s = "";
		// Afficher itinéraires
		if ((h == null) || (h.size() == 0))
			s = "Itinéraire impossible.";
		else {
			for (int i = 0; i < h.size(); i++) {
				List<List<Trajet>> t = h.get(i);
				if (t == null)
					s = "Itinéraire impossible.";
				else {
					s += "\nITINERAIRE " + (i + 1) + "\n----------------";
					for (int k = t.size() - 1; k >= 0; k--) {
						s += "\n\tETAPE " + (t.size() - k) + "\n\t-----------";
						for (Trajet trajet : t.get(k)) {
							s += "\n\t\t" + trajet;
						}
						s += "\n";
					}
				}
			}
		}
		return s;
	}

	/**
	 * Accesseurs de consultation et de modification
	 */

	public List<Trajet>[][] getT() {
		return t;
	}

	public void setT(List<Trajet>[][] t) {
		this.t = t;
	}

	public List<Ville> getV() {
		return v;
	}

	public void setV(List<Ville> v) {
		this.v = v;
	}
}
